home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / lambda.sml < prev    next >
Encoding:
Text File  |  1995-12-30  |  1.2 KB  |  41 lines  |  [TEXT/R*ch]
  1. (* ----- An Interpreter for Call-by-Value lambda-calculus ----- *)
  2.  
  3. datatype ide = IDE of string
  4.  
  5. datatype term = VAR of ide | LAMB of ide * term | APPL of term * term
  6.  
  7. datatype env = ENV of ide -> value
  8.      and value = CLOSURE of term * env
  9.  
  10. exception Unbound_var of string
  11.  
  12. val Arid = ENV(fn (IDE s) => raise Unbound_var s)
  13.  
  14. fun LookUp(ide, ENV f) = f ide
  15.  
  16. fun Extend(ide, value, env) =
  17.       ENV(fn ide' => if ide'=ide then value else LookUp(ide',env))
  18.  
  19. fun Eval(VAR ide, env) = LookUp(ide,env) |
  20.     Eval(lamb as LAMB _, env) = CLOSURE(lamb,env) |
  21.     Eval(APPL(rator,rand), env) = Apply(Eval(rator,env),Eval(rand,env))
  22.  
  23. and Apply(CLOSURE(LAMB(bind,body),env),arg) =
  24.       Eval(body,Extend(bind,arg,env))
  25.  
  26. fun i s = IDE s            (* abbreviation for identifiers *)
  27. and v s = VAR(IDE s)       (* abbreviation for variables *)
  28.  
  29. infix *
  30. fun f * g = APPL(f,g)      (* abbreviation for application *)
  31.  
  32. val I = LAMB(i"a",v"a")                       (* I a = a *)
  33. val K = LAMB(i"a",LAMB(i"b",v"a"))            (* K a b = a *)
  34. val S = LAMB(i"a",LAMB(i"b",LAMB(i"c",        (* S a b c = (a c) (b c) *)
  35.            (v"a" * v"c") * (v"b" * v"c"))))
  36. val D = LAMB(i"a", v"a" * v"a")               (* D a = a a *)
  37.  
  38.  
  39.  
  40.  
  41.